package Interview;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

public class D1 {
	
	public static void subString(String str){
		//TreeMap支持key字典排序，但是由于先要数字排序，所以又定义了ans
		TreeMap<String, Integer> res = new TreeMap<String, Integer>();
		TreeMap<Integer, ArrayList<String>> ans = new TreeMap<Integer,ArrayList<String>>();
		//处理特殊情况
		if(str==""||str==null){
			return;
		}
		if(str.length()==1){
			res.put(str, 1);
		}else{
		String temp = null;
		for (int i = 0; i < str.length()-2;i++) {
			temp = str.substring(i, i+1);
			judgeExist(temp,res);
			temp = str.substring(i, i+2);
			judgeExist(temp,res);
			temp = str.substring(i, i+3);
			judgeExist(temp,res);
		}
		temp = str.substring(str.length()-2,str.length()-1);
		judgeExist(temp,res);
		temp = str.substring(str.length()-1,str.length());
		judgeExist(temp,res);
		temp = str.substring(str.length()-2,str.length());
		judgeExist(temp,res);
	    }
		sort(res, ans);
		print(ans);
    }
	
	//判断key值是否存在
	public static void judgeExist(String str,TreeMap<String, Integer> res){
		if(!res.containsKey(str)){
			res.put(str, 1);
		}else{
			Integer newValue = res.get(str);
			newValue++;
			res.put(str, newValue);
		}
	}
	
	//descendingKeySet逆序打印
	public static void print(TreeMap<Integer, ArrayList<String>> map){
		 Set<Integer> set = map.descendingKeySet();
		 Iterator<Integer> ite = set.iterator ();
		 while(ite.hasNext ()){
			Integer key = ite.next();
			ArrayList<String> arr = map.get(key);
		    for (String string : arr) {
				System.out.println(string+"\t"+key);
			}
		 }
	}
	
	//将出现次数作为key值，key值相同的加入同一个集合中
	public static void sort(TreeMap<String, Integer> res,TreeMap<Integer, ArrayList<String>> ans){
		Set<String> set = res.keySet ();//
		Iterator<String> ite = set.iterator ();
		while(ite.hasNext ()){
			String key = ite.next();
			Integer val = res.get(key);
			if(!ans.containsKey(val)){
				ArrayList<String> arr = new ArrayList<String>();
				arr.add(key);
				ans.put(val,arr);
			}else{
				ArrayList<String> arr = ans.get(val);
				arr.add(key);
			}
	    }
	}
	
	public static void main(String[] args) {
		 subString("abcdefgcsdcsc");
	}
}



















